ТЕОРЕМА ЭЙЛЕРА
В 2007 году исполнится 300 лет со дня рождения
Леонарда Эйлера – одного из величайших
математиков, работы которого оказали решающее влияние на развитие многих современных
разделов математики. Л. Эйлер был действительным членом Петербургской Академии
наук, оказал большое влияние на
развитие отечественной математической школы и в деле подготовки кадров
ученых-математиков и педагогов в России. Поражает своими размерами научное
наследие ученого. При жизни им опубликовано 530 книг и статей, а сейчас их известно
уже более 800. Причем последние 12 лет своей жизни Эйлер тяжело болел, ослеп и,
несмотря на тяжелый недуг, продолжал работать и творить. Статистические подсчеты
показывают, что Эйлер в среднем делал одно открытие в неделю. Трудно найти
математическую проблему, которая не была бы затронута в произведениях Эйлера.
Все математики последующих поколений так или иначе учились у Эйлера, и недаром
известный французский ученый П.С. Лаплас сказал: "Читайте Эйлера, он –
учитель всех нас".
С именем Эйлера, является задача о трех домиках и трех
колодцах.
Задача.
Три соседа имеют три общих колодца. Можно ли провести непересекающиеся
дорожки от каждого дома к каждому колодцу (рис. 1)?
Для
решения этой задачи воспользуемся теоремой, доказанной Эйлером в 1752 году.
Теорема. Если многоугольник разбит на
конечное число многоугольников так, что любые два многоугольника разбиения или
не имеют общих точек, или имеют общие вершины, или имеют общие ребра, то имеет
место равенство
В - Р
+ Г = 1, (*)
где В - общее число вершин, Р - общее число ребер, Г - число
многоугольников (граней).
Доказательство.
Докажем, что равенство (*) не изменится, если в каком-нибудь многоугольнике
данного разбиения провести диагональ (рис. 2, а).
Действительно, после проведения такой диагонали в новом разбиении будет В вершин,
Р+1 ребер и количество многоугольников увеличится на единицу. Следовательно,
имеем
В - (Р + 1) + (Г+1) = В – Р + Г.
Пользуясь
этим свойством, проведем диагонали, разбивающие входящие многоугольники на
треугольники, и для полученного разбиения покажем выполнимость соотношения (*)
(рис. 2, б). Для этого будем последовательно убирать внешние ребра, уменьшая
количество треугольников. При этом возможны два случая:
а) для
удаления треугольника ABC
требуется снять два ребра, в нашем случае AB и BC;
б) для удаления треугольника MKN
требуется снять одно ребро, в нашем случае MN.
В обоих
случаях равенство (*) не изменится. Например, в первом случае после удаления треугольника граф будет состоять из
В-1 вершин, Р-2 ребер и Г-1 многоугольника:
(В - 1) - (Р + 2) + (Г -1) = В – Р + Г.
Самостоятельно рассмотрите второй случай.
Таким образом, удаление одного треугольника не меняет
равенства (*). Продолжая этот процесс удаления треугольников, в конце концов мы
придем к разбиению, состоящему из одного треугольника. Для такого разбиения В
= 3, Р = 3, Г = 1 и, следовательно, B - Р +
Г= 1. Значит, равенство (*) имеет место и для исходного разбиения, откуда
окончательно получаем, что для данного разбиения многоугольника справедливо
соотношение (*).
Заметим, что соотношение Эйлера не зависит от
формы многоугольников. Многоугольники можно деформировать, увеличивать,
уменьшать или даже искривлять их стороны, лишь бы при этом не происходило
разрывов сторон. Соотношение Эйлера при этом не изменится.
Приступим теперь к решению задачи о трех домиках
и трех колодцах.
Решение. Предположим, что это можно
сделать. Отметим домики точками Д1, Д2, Д3, а
колодцы - точками К1, К2, К3 (рис. 1). Каждую
точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые
попарно не пересекаются.
Эти ребра образуют на плоскости многоугольник,
разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно
выполняться соотношение Эйлера В - Р + Г= 1. Добавим к рассматриваемым граням
еще одну - внешнюю часть плоскости по отношению к многоугольнику. Тогда
соотношение Эйлера примет вид В - Р + Г = 2, причем В = 6 и Р = 9. Следовательно,
Г = 5. Каждая из пяти граней имеет по крайней мере четыре ребра, поскольку, по
условию задачи, ни одна из дорожек не должна непосредственно соединять два дома
или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество
ребер должно быть не меньше (5∙4)/2 = 10, что противоречит условию, по
которому их число равно 9. Полученное противоречие показывает, что ответ в
задаче отрицателен - нельзя провести непересекающиеся дорожки от каждого домика
к каждому колодцу.
1. Граф называется связным, если любые две его вершины
можно соединить ломаной, состоящей из ребер графа. Нарисуйте связные и несвязные
графы.
2. Связный граф, не
содержащий ни одной замкнутой ломаной, называется деревом. Нарисуйте графы,
являющиеся деревьями.
3. Докажите, что в графе, являющимся деревом, любые две вершины можно
соединить только одной ломаной.
4. Докажите, что для любого дерева, имеющего В вершин и Р ребер,
справедливо соотношение Эйлера: В - Р = 1.
5. Приведите
примеры графов, для которых В – Р ¹ 1.
6. Граф, не содержащий ни одной замкнутой ломаной, называется лесом.
Пусть лес состоит из n деревьев и имеет В вершин и Р
ребер. Чему равно В - Р?
7. Нарисуйте графы, для которых В - Р равно: а) 0; б) 1;
в) 2; г) -1; д) -2.
8.
Укажите какое-нибудь разбиение выпуклого четырехугольника на выпуклые
четырехугольники.
9.
Докажите, что для произвольного разбиения четырехугольника на четырехугольники
выполняется равенство В – Г = 3.
10.
Укажите какое-нибудь разбиение выпуклого пятиугольника на выпуклые пятиугольники.
11.
Укажите какое-нибудь разбиение треугольника на семиугольники.
12.
Внутри n -
угольника взяты m точек.
Эти точки и вершины многоугольника соединены отрезками так, что исходный многоугольник
разбивается на треугольники. Докажите, что при этом число треугольников равно n + 2m - 2.
13. Многоугольник разбит на конечное
число многоугольников так, что в каждой вершине сходится три ребра. Сколько при
этом имеется вершин и граней, если число ребер равно: а) 6; б) 12; в) 15?
Нарисуйте такие разбиения.
14.
Докажите, что для любого разбиения n-угольника
на m-угольники
выполняется равенство 2В + (2 – m)Г = n + 2.
15. В многоугольнике вырезали дырку в форме многоугольника. Оставшуюся часть разбили на многоугольники. Чему равно В – Р + Г для этого разбиения?
16.
Два соседа имеют: а) три общих колодца; б)
четыре общих колодца. Можно ли провести непересекающиеся дорожки от каждого
дома к каждому колодцу?
17. Три соседа имеют: а) два общих колодца; б) четыре
общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к
каждому колодцу?
18. Четыре соседа имеют четыре общих колодца. Можно ли
провести непересекающиеся дорожки от домиков к колодцам так, чтобы каждый
домик был соединен с тремя колодцами и каждый колодец с тремя домиками?